package algorithm.sort;

import algorithm.RandomArr;

import java.util.Arrays;

public class KuaiSuSort0 {

  int[] a;

  public static void main(String[] args) {
    int[] arr = RandomArr.Arr(100);
    KuaiSuSort0 kuaipai = new KuaiSuSort0();
    kuaipai.a = arr;
    System.out.println(Arrays.toString(kuaipai.a));
//    int sort = kuaipai.kuaisort(0, kuaipai.a.length - 1);
    kuaipai.sort(0, kuaipai.a.length - 1);
    System.out.println(Arrays.toString(kuaipai.a));
  }

  public void sort(int l, int r) {
    if (r <= l) {
      return;
    }
    int mid = kuaisort(l, r);
    sort(l, mid);
    sort(mid + 1, r);
  }

  //从小到大排列
  public int kuaisort(int l, int r) { //l r 分别是数组的左右指针
    //使用第一个元素为基准；
    int base = this.a[l];
    int li = l + 1; //基准不要参与
    int ri = r;
    while (true) {
      while (true) {
        if (this.a[li] >= base || li >= r) { //找到一个 大于等于a，确保li指针左边的都是小于a的数
          break;
        } else {
          li++;
        }
      }
      while (true) {
        if (this.a[ri] < base || ri <= l) { //找到一个 小于a， 确保ri指针右边都是大于等于a的数
          break; //小于a 或者 高位指针达到l 可以break；
        } else {
          ri--;
        }
      }
      if (li >= ri) break;  //指针没有碰撞就交换
      int tmp = this.a[li];
      this.a[li] = this.a[ri];
      this.a[ri] = tmp;
    }
    //交换基准 和 高位指针
    int tmp = this.a[ri];
    this.a[ri] = base;
    this.a[l] = tmp;
    return ri; //返回高位指针
  }

}
